/**
* Created with CLion.
* User:Lenovo
* Date:2023-04-19
* Time:12:39
* Description:单链表
*/

#include "SList.h"

void SLTPrint(SLTNode *pHead)
{
    SLTNode *cur = pHead;// current
    while (cur != NULL)
    {
        printf("%d -> ", cur -> data);
        cur = cur -> next;
    }
    printf("NULL\n");
}

SLTNode *BuyLTNode(SLTDataType x)
{
    SLTNode *newNode = (SLTNode *)malloc(sizeof(SLTNode));
    if (newNode == NULL)
    {
        perror("malloc fail");
        exit(0);
    }
    newNode -> data = x;
    newNode -> next = NULL;

    return newNode;
}

void SLPushFront(SLTNode **ppHead, SLTDataType x)
{
    assert(ppHead);//链表为空，ppHead 也不为空，因为它是头指针 pList 的地址
    /* assert(*ppHead); */ //不能断言，因为链表空了也需要插入
    SLTNode *newNode = BuyLTNode(x);

    newNode -> next = *ppHead;
    *ppHead = newNode;
}

void SLPushBack(SLTNode **ppHead, SLTDataType x)
{
    assert(ppHead);
    SLTNode *newNode = BuyLTNode(x);

    if (*ppHead == NULL)
    {
        *ppHead = newNode;//改变结构体的指针 - 在函数里改变什么，就得用它的地址 - 二级指针
    }
    else
    {
        SLTNode *tail = *ppHead;
        while (tail -> next != NULL)
        {
            tail = tail -> next;
        }
        tail -> next = newNode;//链接新节点
    }
    //头插每次都要用二级指针，但是尾插不用
}

void SLPopFront(SLTNode **ppHead)
{
    assert(ppHead);
    assert(*ppHead);//链表为空，不能头删

    SLTNode *tmp = (*ppHead) -> next;
    free(*ppHead);
    *ppHead = tmp;
}

void SLPopBack(SLTNode **ppHead)
{
    assert(ppHead);
    //没有节点
    assert(*ppHead);

    //一个节点
    if ((*ppHead) -> next == NULL)
    {
        free(*ppHead);
        *ppHead = NULL;
    }

    //多个节点
    else
    {
        // 1.
        /*
        SLTNode *prev = NULL;
        SLTNode *tail = *ppHead;
        while (tail -> next)
        {
            prev = tail;
            tail = tail -> next;
        }
        free(tail);
        prev -> next = NULL;
        */

        // 2.
        SLTNode *tail = *ppHead;
        while (tail -> next -> next)
        {
            tail = tail -> next;
        }
        free(tail -> next);
        tail -> next = NULL;

        //如果链表只有一个节点，上面的两个方法都会出现问题 - 对空指针进行的操作
    }
}

SLTNode *STFind(SLTNode *pHead, SLTDataType x)
{
    SLTNode *cur = pHead;
    while (cur)
    {
        if (cur -> data == x)
        {
            return cur;
        }
        cur = cur -> next;
    }
    return NULL;
}

void SLInsert(SLTNode **ppHead, SLTNode *pos, SLTDataType x) //在 pos 之前插入
{
    assert(ppHead);
    assert(pos);

    if (*ppHead == pos)
    {
        SLPushFront(ppHead, x);
    }
    else
    {
        SLTNode *prev = *ppHead;
        while (prev && prev -> next != pos)
        {
            prev = prev -> next;
        }
        if (!prev)
        {
            printf("pos 输入有误\n");
            return;
        }
        SLTNode *newNode = BuyLTNode(x);
        newNode -> next = pos;
        prev -> next = newNode;
    }

}

void SLInsertAfter(SLTNode *pos, SLTDataType x)
{
    assert(pos);

    SLTNode *newNode = BuyLTNode(x);
    newNode -> next = pos -> next;
    pos -> next = newNode;
}

void SLErase(SLTNode **ppHead, SLTNode *pos) //删除 pos 位置的值
{
    assert(ppHead);
    assert(pos);

    if (pos == *ppHead)
    {
        SLPopFront(ppHead);
    }
    else
    {
        SLTNode *prev = *ppHead;
        while (prev && prev -> next != pos)
        {
            prev = prev -> next;
        }
        if (!prev)
        {
            printf("pos 输入有误\n");
            return;
        }

        prev -> next = pos -> next;
        free(pos);
        pos = NULL;
    }
}

void SLEraseAfter(SLTNode *pos)
{
    assert(pos);
    assert(pos -> next);

    SLTNode *next = pos -> next;
    pos -> next = pos -> next -> next;
    free(next);
}

void SLDestroy(SLTNode **ppHead)
{
    assert(ppHead);
    SLTNode *cur = *ppHead;
    while (cur)
    {
        SLTNode *next = cur -> next;
        free(cur);
        cur = next;
    }
    *ppHead = NULL;
}